package tree

func BfsTraversal(root *Node) [][]int {
	// 通过上一层的长度确定下一层的元素
	result := make([][]int, 0)
	if root == nil {
		return result
	}

	queue := make([]*Node, 0)
	//先存入根节点
	queue = append(queue, root)

	for len(queue) > 0 {
		list := make([]int, 0)

		//取这一层的队列的长度
		l := len(queue)
		//遍历当前层，再添加下一层
		for i := 0; i < l; i++ {
			//pop
			level := queue[0]
			queue = queue[1:]

			//存入每行的值
			list = append(list, level.Val)

			//存入子节点 |
			if level.Left != nil {
				queue = append(queue, level.Left)
			}
			if level.Right != nil {
				queue = append(queue, level.Right)
			}

		} // end 每一层

		result = append(result, list)
	}

	return result
}
